import java.util.LinkedList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * 
 */
class Solution2 {
    public List<Integer> findAnagrams(String ss, String pp) {
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        int[] hashS = new int[26], hashP = new int[26];
        int n = p.length, count = 0;
        List<Integer> ret = new LinkedList<>();

        // 在hash表中统计p的字符个数
        for(int i = 0; i < n; i++) {
            int index = p[i] - 'a';
            hashP[index]++;
        }

        for(int left = 0, right = 0; right < s.length; right++) {
            // 进窗口
            int index = s[right] - 'a';
            hashS[index]++;
            // 维护有效字符个数count
            if(hashS[index] <= hashP[index]) count++;

            // 判断
            if(count == n) ret.add(left);

            // 出窗口
            if(right - left + 1 >= n) {
                // 维护有效字符个数count
                int tmp = s[left] - 'a';
                if(hashS[tmp] <= hashP[tmp]) count--;
                hashS[tmp]--;
                left++;
            }
        }

        return ret;
    }
}